package 算法.练习1;

import 算法.NiuKe.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author:谢君臣
 * @Date:2021/7/27-19:54
 * @version:1.0
 * @function:
 */
public class NC45 {
    public int[][] threeOrders (TreeNode root) {
        // write code here
        List<Integer> pre = PRE(root);
        List<Integer> in = IN(root);
        List<Integer> post = POST(root);
        int len = pre.size();
        int [][]res = new int[3][len];
        for(int i = 0;i<len;i++){
            res[0][i] = pre.get(i);
        }
        for(int i = 0;i<len;i++){
            res[1][i] = in.get(i);
        }
        for(int i = 0;i<len;i++){
            res[2][i] = post.get(i);
        }
        return res;
    }
    private List<Integer> PRE(TreeNode root){
        ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node.right!=null) stack.add(node.right);
            if (node.left!=null) stack.add(node.left);
            list.add(node.val);
        }
        return list;
    }
    private List<Integer> IN(TreeNode root){
        ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty()||root!=null){
            while (root!=null){
                stack.add(root);
                root = root.left;
            }
            if (!stack.isEmpty()){
                TreeNode node = stack.pop();
                if (node.right!=null) root = node.right;
//                else root = null;
                list.add(node.val);
            }
        }
        return list;
    }
    private List<Integer> POST(TreeNode root){
        ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> temp = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node.left!=null) stack.add(node.left);
            if (node.right!=null) stack.add(node.right);
            temp.add(node.val);
        }
        while (!temp.isEmpty())list.add(temp.pop());
        return list;
    }
}
